package lcof;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import jdk.management.resource.internal.inst.FileOutputStreamRMHooks;

import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: lcof
 * @Author: 江岸
 * @CreateTime: 2021-05-09 23:24
 * @Description: 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindContinuousSequence57 {

    public static int[][] findContinuousSequence(int target) {
        ArrayList<int[]> arrayList = new ArrayList<>();
        for (int i=1;i<=target/2;i++){
            int temp = i;
            int res = temp;
            while (res<target){
                temp++;
                res+=temp;
            }
            if (res==target){
                int[] ints = new int[temp - i + 1];
                for (int j=0;j<ints.length;j++){
                    ints[j] = j+i;
                }
                arrayList.add(ints);
            }
        }
        for (int[] arr:arrayList){
            System.out.println(Arrays.toString(arr));
        }
        int[][] res = new int[arrayList.size()][];
        return arrayList.toArray(res);
    }

    public static void main(String[] args) {
        int[][] continuousSequence = findContinuousSequence(15);
        System.out.println(Arrays.toString(continuousSequence));
    }

    //滑动窗口 双指针
    public int[][] findContinuousSequence2(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        //toArray(new T[0])能够运行是因为java做了优化，能动态生成对应大小的数组，是官方建议的书写方式，能避免某些并发问题并且效率更高
        return res.toArray(new int[0][]);
    }

}
